class Solution {
    int[] temp;
    public int[] sortArray(int[] nums) {
        temp=new int[nums.length];
        mergeSort(nums,0,nums.length-1);
        return nums;
    }
    public void mergeSort(int[] nums,int l,int r){
        if(l>=r) return;
        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);
        int cur1=l,cur2=mid+1,i=0;
        while(cur1<=mid&&cur2<=r)
            temp[i++]=nums[cur1]<=nums[cur2]?nums[cur1++]:nums[cur2++];
        while(cur1<=mid)
            temp[i++]=nums[cur1++];
        while(cur2<=r)
            temp[i++]=nums[cur2++];
        for(int j=l;j<=r;j++)
            nums[j]=temp[j-l];
    }
}